#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MaxSize 10
//单链表
typedef struct LNode{
    int data;
    struct LNode *next;
} LNode, *LinkList;
//双链表
typedef struct DNode{
    int data;
    struct DNode *prior, *next;
} DNode, *DLinklist;
//静态链表
struct Node{
    int data;
    int next;
}SLinkList[MaxSize];

//初始化(带头结点)
bool InitList1(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    if(L==NULL){
        return false;
    }
    L->next = NULL;
    return true;
}
// 初始化(不带头结点)
bool InitList2(LinkList &L)
{
    L = NULL;
    return true;
}
// 判断是否为空(带头结点)
bool Empty1(LinkList L){
    if(L->next==NULL){
        return true;
    }
    else {
        return false;
    }
}
// 判断是否为空(不带头结点)
bool Empty2(LinkList L)
{
    if (L == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}
//求链表的长度(带头结点)
int Length1(LinkList L){
    int len=0;
    LNode *p=L;
    while(p->next!=NULL){
        p=p->next;
        len++;
    }
    return len;
}
// 求链表的长度(不带头结点)
int Length2(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p!= NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}
// 按位查找,返回第i个结点(带头结点)
LNode *GetElem1(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    LNode *p = L; // 指针p指向当前扫到的结点
    int j = 0;    // 当前p指向的是第几个结点
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}
// 按位查找,返回第i个结点(不带头结点)
LNode *GetElem2(LinkList L, int i)
{
    if (i < 0)
    {
        return NULL;
    }
    LNode *p = L; // 指针p指向当前扫到的结点
    int j = 1;    // 当前p指向的是第几个结点
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}
//按值查找(带头结点)
LNode *LocateElem1(LinkList L,int e){
    LNode *p=L->next;
    while(p!=NULL && p->data!=e){
        p=p->next;
    }
    return p;
}
// 按值查找(不带头结点)
LNode *LocateElem2(LinkList L, int e)
{
    LNode *p = L;
    while (p != NULL && p->data != e)
    {
        p = p->next;
    }
    return p;
}
    // 指定结点的后插操作
    bool InsertNextNode(LNode *p, int e)
{
    if (p == NULL)
    {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
    {
        return false;
    }
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
// 指定结点的前插操作

// 对指定结点前插操作需要知道头结点的位置,然后经过时间复杂度为O(n)找到指定结点的前一个结点,对其进行后插操作,单链表的局限

//优化时间复杂度为O(1) =>将结点后插,再将新建的结点与指定的结点数据交换
bool InsertPoriorNode(LNode *p,int e){
    if(p==NULL){
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if(s==NULL){
        return false;
    }
    s->next = p->next;
    p->next=s;
    s->data = p->data;
    p->data=e;
    return true;
}
// 按位序插入(带头结点)
bool ListInsert1(LinkList &L,int i,int e){
    if(i<1){
        return false;
    }
    LNode *p;//指针P指向当前扫过的结点
    int j = 0;
    p = L;
    while(p != NULL && j < i-1){
        p = p->next;
        j++;
    }
   /* if(p == NULL){
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next = p->next;
    p->next = s;
    return true;*/
    //经过上述一系列操作,得到的p可能为NULL,在InsertNextNode函数中也有考虑
    return InsertNextNode(p, e);
}
// 按位序插入(不带头结点)
bool ListInsert2(LinkList &L, int i, int e)
{
    if (i < 1)
    {
        return false;
    }
    // 处理插入到第一个位置的情况（不带头结点需特殊处理）
    if (i == 1)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L; // 新节点指向原头节点
        L = s;       // 更新头指针为新节点
        return true;
    }
    LNode *p = L; // p从第一个节点开始遍历
    int j = 1;    // 当前p的位置是第1个节点
    // 寻找第i-1个节点（需移动i-2次）
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    { // i-1位置超出链表长度
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
//按位序删除(带头结点)
bool ListDelete1(LinkList &L,int i,int &e){
    if(i<1){
        return false;
    }
    LNode *p=L;//指针P指向当前扫过的结点
    int j = 0;//当前p指向的是第几个结点
    while(p!=NULL && j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL){
        return false;
    }
    if(p->next==NULL){
        return false;
    }
    LNode *q = p->next;//q指向被删的结点
    e=q->data;//用e返回元素的值
    p->next = q->next;
    free(q);
    return true;
}
// 按位序删除(不带头结点)
bool ListDelete2(LinkList &L, int i, int &e)
{
    if (i < 1)
    {
        return false;
    }
    if(i==1){
        if(L==NULL){
            return false;
        }
        LNode *s = L; // s指向被删的结点
        e = s->data;  // 用e返回元素的值
        L=s->next;
        free(s);
        return true;
    }
    LNode *p=L;  // 指针P指向当前扫过的结点
    int j = 1; // 当前p指向的是第几个结点
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
    {
        return false;
    }
    if (p->next == NULL)
    {
        return false;
    }
    LNode *q = p->next; // q指向被删的结点
    e = q->data;        // 用e返回元素的值
    p->next = q->next;
    free(q);
    return true;
}
//指定结点的删除
//单链表的局限性,无法逆向检索,如果是删除最后一个节点,只能从头检索,时间复杂度O(n),除了删除最后一个结点外都可以优化为O(1)
bool DeleteNode(LNode *p){
    if(p==NULL){
        return false;
    }
    LNode *q=p->next;
    p->data=q->data;
    p->next = q->next;
    free(q);
    return true;
}
//尾插法建立单链表(带头结点)
LinkList List_Tailnsert1(LinkList &L){
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;//r为表尾指针
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        r->next=s;
        r=s;//r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next=NULL;
    return L;
}
// 尾插法建立单链表(不带头结点)
LinkList List_TailInsert2(LinkList &L)
{
    int x;
    L = NULL;            // 初始化为空，不带头结点
    LNode *s, *r = NULL; // 尾指针r初始化为NULL
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = NULL; // 新节点的next置为NULL
        if (L == NULL)
        { // 链表为空时，L和r均指向第一个节点
            L = s;
            r = s;
        }
        else
        { // 否则插入到尾部并更新尾指针
            r->next = s;
            r = s;
        }
        scanf("%d", &x);
    }
    // r->next = NULL;
    // 不能再末尾设置r->next = NULL;需要再每个新节点后都添加,否则如果输入9999,直接执行r->next = NULL;r是空指针会导致程序崩溃
    return L;
}
//头插法建立单链表(带头结点)
LinkList List_HeadInsert1(LinkList &L){
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 头插法建立单链表(不带头结点)
LinkList List_HeadInsert2(LinkList &L)
{
    LNode *s;
    int x;
    L = NULL; // 初始化为空链表，无头结点
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L; // 新节点指向原头节点（或NULL）
        L = s;       // 更新头指针L指向新节点
        scanf("%d", &x);
    }
    return L;
}
//逆置(带头结点)
void reverseList1(LinkList &head)
{
    if (head == NULL || head->next == NULL)
    {
        return; // 空链表或仅头节点无需处理
    }
    LNode *current = head->next; // 原链表的第一个节点
    head->next = NULL;          // 断开原链表
    LNode *next_node;
    while (current != NULL)
    {
        next_node = current->next;  // 保存下一个节点
        current->next = head->next; // 将current插入到头部
        head->next = current;
        current = next_node; // 处理下一个节点
    }
}

// 逆置(不带头结点)
void reverseList2(LinkList &head_ref)
{
    LNode *prev = NULL;
    LNode *current = head_ref;
    LNode *next_node = NULL;
    while (current != NULL)
    {

        next_node = current->next; // 保存下一个节点
        current->next = prev;      // 反转当前节点的指针
        prev = current;            // prev前移
        current = next_node;       // current前移
    }
    head_ref = prev; // 更新头指针为新链表的第一个节点
}

//双链表操作

//初始化双链表
bool InitDLinklist(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL){
        return false;
    }
    L->prior=NULL;
    L->next = NULL;
    return true;
}
//判断双链表是否为空
bool Empty(DLinklist &L){
    if(L->next == NULL){
        return true;
    }
    else{
        return false;
    }
}
//在双链表p结点之后插s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if(p==NULL || s==NULL){
        return false;
    }
    s->next = p->next;
    if(p->next!=NULL){//如果利用循环列表就不用考虑
        p->next->prior = s;
    }
    s->prior=p;
    p->next = s;
    return true;
}
//在双链表中删除p结点的后继结点
bool DeleteNextDNode(DNode *p){
    if(p==NULL){
        return false;
    }
    DNode *q = p->next;
    if(q==NULL){
        return false;
    }
    p->next = q->next;
    if(q->next!=NULL){
        q->next->prior = p;//如果利用循环列表就不用考虑
    }
    free(q);
    return true;
}
// 利用DeleteNextDNode函数释放双链表
void DestoryList(DLinklist &L){
    while(L->next!=NULL){
        DeleteNextDNode(L);
    }
    free(L);
    L = NULL;
}
// 尾插法建立双链表(带头结点)
DLinklist DList_Tailnsert1(DLinklist &L)
{
    int x;
    L = (DLinklist)malloc(sizeof(DNode));
    L->prior = NULL;
    DNode *s, *r = L; // r为表尾指针
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        r->next = s;
        s->prior = r;
        r = s; // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
// 尾插法建立双链表(不带头结点)
DLinklist DList_TailInsert2(DLinklist &L)
{
    int x;
    L = NULL;            // 初始化为空，不带头结点
    DNode *s, *r = NULL; // 尾指针r初始化为NULL
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = NULL; // 新节点的next置为NULL
        s->prior = r;
        if (L == NULL)
        { // 链表为空时，L和r均指向第一个节点
            L = s;
            r = s;
        }
        else
        { // 否则插入到尾部并更新尾指针
            r->next = s;
            r = s;
        }
        scanf("%d", &x);
    }
    // r->next = NULL;
    // 不能再末尾设置r->next = NULL;需要再每个新节点后都添加,否则如果输入9999,直接执行r->next = NULL;r是空指针会导致程序崩溃
    return L;
}

// 头插法建立双链表(带头结点)
DLinklist DList_HeadInsert1(DLinklist &L)
{
    DNode *s;
    int x;
    L = (DLinklist)malloc(sizeof(DNode));
    L->next = NULL;
    L->prior = NULL;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = L->next;
        s->prior = L;
        if(L->next!=NULL){
            L->next->prior = s;
        }
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 头插法建立双链表(不带头结点)
DLinklist DList_HeadInsert2(DLinklist &L)
{
    DNode *s;
    int x;
    L = NULL; // 初始化为空链表，无头结点
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        s->next = L; // 新节点指向原头节点（或NULL）
        s->prior = NULL;
        if(L!=NULL){
            L->prior = s;
        }
        L = s;
        scanf("%d", &x);
    }
    return L;
}

